/*
 * ORACLE PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 */

/*
 *
 *
 *
 *
 *
 * Written by Doug Lea with assistance from members of JCP JSR-166
 * Expert Group and released to the public domain, as explained at
 * http://creativecommons.org/publicdomain/zero/1.0/
 */

package java.util.concurrent.locks;

import java.util.concurrent.TimeUnit;
import java.util.Collection;

/**
 * An implementation of {@link ReadWriteLock} supporting similar
 * semantics to {@link ReentrantLock}.
 * <p>This class has the following properties:
 *
 * <ul>
 * <li><b>Acquisition order</b>
 *
 * <p>This class does not impose a reader or writer preference
 * ordering for lock access.  However, it does support an optional
 * <em>fairness</em> policy.
 *
 * <dl>
 * <dt><b><i>Non-fair mode (default)</i></b>
 * <dd>When constructed as non-fair (the default), the order of entry
 * to the read and write lock is unspecified, subject to reentrancy
 * constraints.  A nonfair lock that is continuously contended may
 * indefinitely postpone one or more reader or writer threads, but
 * will normally have higher throughput than a fair lock.
 *
 * <dt><b><i>Fair mode</i></b>
 * <dd>When constructed as fair, threads contend for entry using an
 * approximately arrival-order policy. When the currently held lock
 * is released, either the longest-waiting single writer thread will
 * be assigned the write lock, or if there is a group of reader threads
 * waiting longer than all waiting writer threads, that group will be
 * assigned the read lock.
 *
 * <p>A thread that tries to acquire a fair read lock (non-reentrantly)
 * will block if either the write lock is held, or there is a waiting
 * writer thread. The thread will not acquire the read lock until
 * after the oldest currently waiting writer thread has acquired and
 * released the write lock. Of course, if a waiting writer abandons
 * its wait, leaving one or more reader threads as the longest waiters
 * in the queue with the write lock free, then those readers will be
 * assigned the read lock.
 *
 * <p>A thread that tries to acquire a fair write lock (non-reentrantly)
 * will block unless both the read lock and write lock are free (which
 * implies there are no waiting threads).  (Note that the non-blocking
 * {@link ReadLock#tryLock()} and {@link WriteLock#tryLock()} methods
 * do not honor this fair setting and will immediately acquire the lock
 * if it is possible, regardless of waiting threads.)
 * <p>
 * </dl>
 *
 * <li><b>Reentrancy</b>
 *
 * <p>This lock allows both readers and writers to reacquire read or
 * write locks in the style of a {@link ReentrantLock}. Non-reentrant
 * readers are not allowed until all write locks held by the writing
 * thread have been released.
 *
 * <p>Additionally, a writer can acquire the read lock, but not
 * vice-versa.  Among other applications, reentrancy can be useful
 * when write locks are held during calls or callbacks to methods that
 * perform reads under read locks.  If a reader tries to acquire the
 * write lock it will never succeed.
 *
 * <li><b>Lock downgrading</b>
 * <p>Reentrancy also allows downgrading from the write lock to a read lock,
 * by acquiring the write lock, then the read lock and then releasing the
 * write lock. However, upgrading from a read lock to the write lock is
 * <b>not</b> possible.
 *
 * <li><b>Interruption of lock acquisition</b>
 * <p>The read lock and write lock both support interruption during lock
 * acquisition.
 *
 * <li><b>{@link Condition} support</b>
 * <p>The write lock provides a {@link Condition} implementation that
 * behaves in the same way, with respect to the write lock, as the
 * {@link Condition} implementation provided by
 * {@link ReentrantLock#newCondition} does for {@link ReentrantLock}.
 * This {@link Condition} can, of course, only be used with the write lock.
 *
 * <p>The read lock does not support a {@link Condition} and
 * {@code readLock().newCondition()} throws
 * {@code UnsupportedOperationException}.
 *
 * <li><b>Instrumentation</b>
 * <p>This class supports methods to determine whether locks
 * are held or contended. These methods are designed for monitoring
 * system state, not for synchronization control.
 * </ul>
 *
 * <p>Serialization of this class behaves in the same way as built-in
 * locks: a deserialized lock is in the unlocked state, regardless of
 * its state when serialized.
 *
 * <p><b>Sample usages</b>. Here is a code sketch showing how to perform
 * lock downgrading after updating a cache (exception handling is
 * particularly tricky when handling multiple locks in a non-nested
 * fashion):
 *
 * <pre> {@code
 * class CachedData {
 *   Object data;
 *   volatile boolean cacheValid;
 *   final ReentrantReadWriteLock rwl = new ReentrantReadWriteLock();
 *
 *   void processCachedData() {
 *     rwl.readLock().lock();
 *     if (!cacheValid) {
 *       // Must release read lock before acquiring write lock
 *       rwl.readLock().unlock();
 *       rwl.writeLock().lock();
 *       try {
 *         // Recheck state because another thread might have
 *         // acquired write lock and changed state before we did.
 *         if (!cacheValid) {
 *           data = ...
 *           cacheValid = true;
 *         }
 *         // Downgrade by acquiring read lock before releasing write lock
 *         rwl.readLock().lock();
 *       } finally {
 *         rwl.writeLock().unlock(); // Unlock write, still hold read
 *       }
 *     }
 *
 *     try {
 *       use(data);
 *     } finally {
 *       rwl.readLock().unlock();
 *     }
 *   }
 * }}</pre>
 *
 * ReentrantReadWriteLocks can be used to improve concurrency in some
 * uses of some kinds of Collections. This is typically worthwhile
 * only when the collections are expected to be large, accessed by
 * more reader threads than writer threads, and entail operations with
 * overhead that outweighs synchronization overhead. For example, here
 * is a class using a TreeMap that is expected to be large and
 * concurrently accessed.
 *
 * <pre> {@code
 * class RWDictionary {
 *   private final Map<String, Data> m = new TreeMap<String, Data>();
 *   private final ReentrantReadWriteLock rwl = new ReentrantReadWriteLock();
 *   private final Lock r = rwl.readLock();
 *   private final Lock w = rwl.writeLock();
 *
 *   public Data get(String key) {
 *     r.lock();
 *     try { return m.get(key); }
 *     finally { r.unlock(); }
 *   }
 *   public String[] allKeys() {
 *     r.lock();
 *     try { return m.keySet().toArray(); }
 *     finally { r.unlock(); }
 *   }
 *   public Data put(String key, Data value) {
 *     w.lock();
 *     try { return m.put(key, value); }
 *     finally { w.unlock(); }
 *   }
 *   public void clear() {
 *     w.lock();
 *     try { m.clear(); }
 *     finally { w.unlock(); }
 *   }
 * }}</pre>
 *
 * <h3>Implementation Notes</h3>
 *
 * <p>This lock supports a maximum of 65535 recursive write locks
 * and 65535 read locks. Attempts to exceed these limits result in
 * {@link Error} throws from locking methods.
 *
 * @author Doug Lea
 * @since 1.5
 */
public class ReentrantReadWriteLock
    implements ReadWriteLock, java.io.Serializable {

  private static final long serialVersionUID = -6992448646407690164L;
  /**
   * Inner class providing readlock
   */
  private final ReentrantReadWriteLock.ReadLock readerLock;
  /**
   * Inner class providing writelock
   */
  private final ReentrantReadWriteLock.WriteLock writerLock;
  /**
   * Performs all synchronization mechanics
   */
  final Sync sync;

  /**
   * Creates a new {@code ReentrantReadWriteLock} with
   * default (nonfair) ordering properties.
   */
  public ReentrantReadWriteLock() {
    this(false);
  }

  /**
   * Creates a new {@code ReentrantReadWriteLock} with
   * the given fairness policy.
   *
   * @param fair {@code true} if this lock should use a fair ordering policy
   */
  public ReentrantReadWriteLock(boolean fair) {
    sync = fair ? new FairSync() : new NonfairSync();
    readerLock = new ReadLock(this);
    writerLock = new WriteLock(this);
  }

  public ReentrantReadWriteLock.WriteLock writeLock() {
    return writerLock;
  }

  public ReentrantReadWriteLock.ReadLock readLock() {
    return readerLock;
  }

  /**
   * Synchronization implementation for ReentrantReadWriteLock.
   * Subclassed into fair and nonfair versions.
   */
  abstract static class Sync extends AbstractQueuedSynchronizer {

    private static final long serialVersionUID = 6317671515068378041L;

        /*
         * Read vs write count extraction constants and functions.
         * Lock state is logically divided into two unsigned shorts:
         * The lower one representing the exclusive (writer) lock hold count,
         * and the upper the shared (reader) hold count.
         */

    static final int SHARED_SHIFT = 16;
    static final int SHARED_UNIT = (1 << SHARED_SHIFT);
    static final int MAX_COUNT = (1 << SHARED_SHIFT) - 1;
    static final int EXCLUSIVE_MASK = (1 << SHARED_SHIFT) - 1;

    /**
     * Returns the number of shared holds represented in count
     */
    static int sharedCount(int c) {
      return c >>> SHARED_SHIFT;
    }

    /**
     * Returns the number of exclusive holds represented in count
     */
    static int exclusiveCount(int c) {
      return c & EXCLUSIVE_MASK;
    }

    /**
     * A counter for per-thread read hold counts.
     * Maintained as a ThreadLocal; cached in cachedHoldCounter
     */
    static final class HoldCounter {

      int count = 0;
      // Use id, not reference, to avoid garbage retention
      final long tid = getThreadId(Thread.currentThread());
    }

    /**
     * ThreadLocal subclass. Easiest to explicitly define for sake
     * of deserialization mechanics.
     */
    static final class ThreadLocalHoldCounter
        extends ThreadLocal<HoldCounter> {

      public HoldCounter initialValue() {
        return new HoldCounter();
      }
    }

    /**
     * The number of reentrant read locks held by current thread.
     * Initialized only in constructor and readObject.
     * Removed whenever a thread's read hold count drops to 0.
     */
    private transient ThreadLocalHoldCounter readHolds;

    /**
     * The hold count of the last thread to successfully acquire
     * readLock. This saves ThreadLocal lookup in the common case
     * where the next thread to release is the last one to
     * acquire. This is non-volatile since it is just used
     * as a heuristic, and would be great for threads to cache.
     *
     * <p>Can outlive the Thread for which it is caching the read
     * hold count, but avoids garbage retention by not retaining a
     * reference to the Thread.
     *
     * <p>Accessed via a benign data race; relies on the memory
     * model's final field and out-of-thin-air guarantees.
     */
    private transient HoldCounter cachedHoldCounter;

    /**
     * firstReader is the first thread to have acquired the read lock.
     * firstReaderHoldCount is firstReader's hold count.
     *
     * <p>More precisely, firstReader is the unique thread that last
     * changed the shared count from 0 to 1, and has not released the
     * read lock since then; null if there is no such thread.
     *
     * <p>Cannot cause garbage retention unless the thread terminated
     * without relinquishing its read locks, since tryReleaseShared
     * sets it to null.
     *
     * <p>Accessed via a benign data race; relies on the memory
     * model's out-of-thin-air guarantees for references.
     *
     * <p>This allows tracking of read holds for uncontended read
     * locks to be very cheap.
     */
    private transient Thread firstReader = null;
    private transient int firstReaderHoldCount;

    Sync() {
      readHolds = new ThreadLocalHoldCounter();
      setState(getState()); // ensures visibility of readHolds
    }

        /*
         * Acquires and releases use the same code for fair and
         * nonfair locks, but differ in whether/how they allow barging
         * when queues are non-empty.
         */

    /**
     * Returns true if the current thread, when trying to acquire
     * the read lock, and otherwise eligible to do so, should block
     * because of policy for overtaking other waiting threads.
     */
    abstract boolean readerShouldBlock();

    /**
     * Returns true if the current thread, when trying to acquire
     * the write lock, and otherwise eligible to do so, should block
     * because of policy for overtaking other waiting threads.
     */
    abstract boolean writerShouldBlock();

        /*
         * Note that tryRelease and tryAcquire can be called by
         * Conditions. So it is possible that their arguments contain
         * both read and write holds that are all released during a
         * condition wait and re-established in tryAcquire.
         */

    protected final boolean tryRelease(int releases) {
      if (!isHeldExclusively()) {
        throw new IllegalMonitorStateException();
      }
      int nextc = getState() - releases;
      boolean free = exclusiveCount(nextc) == 0;
      if (free) {
        setExclusiveOwnerThread(null);
      }
      setState(nextc);
      return free;
    }

    protected final boolean tryAcquire(int acquires) {
            /*
             * Walkthrough:
             * 1. If read count nonzero or write count nonzero
             *    and owner is a different thread, fail.
             * 2. If count would saturate, fail. (This can only
             *    happen if count is already nonzero.)
             * 3. Otherwise, this thread is eligible for lock if
             *    it is either a reentrant acquire or
             *    queue policy allows it. If so, update state
             *    and set owner.
             */
      Thread current = Thread.currentThread();
      int c = getState();
      int w = exclusiveCount(c);
      if (c != 0) {
        // (Note: if c != 0 and w == 0 then shared count != 0)
        if (w == 0 || current != getExclusiveOwnerThread()) {
          return false;
        }
        if (w + exclusiveCount(acquires) > MAX_COUNT) {
          throw new Error("Maximum lock count exceeded");
        }
        // Reentrant acquire
        setState(c + acquires);
        return true;
      }
      if (writerShouldBlock() ||
          !compareAndSetState(c, c + acquires)) {
        return false;
      }
      setExclusiveOwnerThread(current);
      return true;
    }

    protected final boolean tryReleaseShared(int unused) {
      Thread current = Thread.currentThread();
      if (firstReader == current) {
        // assert firstReaderHoldCount > 0;
        if (firstReaderHoldCount == 1) {
          firstReader = null;
        } else {
          firstReaderHoldCount--;
        }
      } else {
        HoldCounter rh = cachedHoldCounter;
        if (rh == null || rh.tid != getThreadId(current)) {
          rh = readHolds.get();
        }
        int count = rh.count;
        if (count <= 1) {
          readHolds.remove();
          if (count <= 0) {
            throw unmatchedUnlockException();
          }
        }
        --rh.count;
      }
      for (; ; ) {
        int c = getState();
        int nextc = c - SHARED_UNIT;
        if (compareAndSetState(c, nextc))
        // Releasing the read lock has no effect on readers,
        // but it may allow waiting writers to proceed if
        // both read and write locks are now free.
        {
          return nextc == 0;
        }
      }
    }

    private IllegalMonitorStateException unmatchedUnlockException() {
      return new IllegalMonitorStateException(
          "attempt to unlock read lock, not locked by current thread");
    }

    protected final int tryAcquireShared(int unused) {
            /*
             * Walkthrough:
             * 1. If write lock held by another thread, fail.
             * 2. Otherwise, this thread is eligible for
             *    lock wrt state, so ask if it should block
             *    because of queue policy. If not, try
             *    to grant by CASing state and updating count.
             *    Note that step does not check for reentrant
             *    acquires, which is postponed to full version
             *    to avoid having to check hold count in
             *    the more typical non-reentrant case.
             * 3. If step 2 fails either because thread
             *    apparently not eligible or CAS fails or count
             *    saturated, chain to version with full retry loop.
             */
      Thread current = Thread.currentThread();
      int c = getState();
      if (exclusiveCount(c) != 0 &&
          getExclusiveOwnerThread() != current) {
        return -1;
      }
      int r = sharedCount(c);
      if (!readerShouldBlock() &&
          r < MAX_COUNT &&
          compareAndSetState(c, c + SHARED_UNIT)) {
        if (r == 0) {
          firstReader = current;
          firstReaderHoldCount = 1;
        } else if (firstReader == current) {
          firstReaderHoldCount++;
        } else {
          HoldCounter rh = cachedHoldCounter;
          if (rh == null || rh.tid != getThreadId(current)) {
            cachedHoldCounter = rh = readHolds.get();
          } else if (rh.count == 0) {
            readHolds.set(rh);
          }
          rh.count++;
        }
        return 1;
      }
      return fullTryAcquireShared(current);
    }

    /**
     * Full version of acquire for reads, that handles CAS misses
     * and reentrant reads not dealt with in tryAcquireShared.
     */
    final int fullTryAcquireShared(Thread current) {
            /*
             * This code is in part redundant with that in
             * tryAcquireShared but is simpler overall by not
             * complicating tryAcquireShared with interactions between
             * retries and lazily reading hold counts.
             */
      HoldCounter rh = null;
      for (; ; ) {
        int c = getState();
        if (exclusiveCount(c) != 0) {
          if (getExclusiveOwnerThread() != current) {
            return -1;
          }
          // else we hold the exclusive lock; blocking here
          // would cause deadlock.
        } else if (readerShouldBlock()) {
          // Make sure we're not acquiring read lock reentrantly
          if (firstReader == current) {
            // assert firstReaderHoldCount > 0;
          } else {
            if (rh == null) {
              rh = cachedHoldCounter;
              if (rh == null || rh.tid != getThreadId(current)) {
                rh = readHolds.get();
                if (rh.count == 0) {
                  readHolds.remove();
                }
              }
            }
            if (rh.count == 0) {
              return -1;
            }
          }
        }
        if (sharedCount(c) == MAX_COUNT) {
          throw new Error("Maximum lock count exceeded");
        }
        if (compareAndSetState(c, c + SHARED_UNIT)) {
          if (sharedCount(c) == 0) {
            firstReader = current;
            firstReaderHoldCount = 1;
          } else if (firstReader == current) {
            firstReaderHoldCount++;
          } else {
            if (rh == null) {
              rh = cachedHoldCounter;
            }
            if (rh == null || rh.tid != getThreadId(current)) {
              rh = readHolds.get();
            } else if (rh.count == 0) {
              readHolds.set(rh);
            }
            rh.count++;
            cachedHoldCounter = rh; // cache for release
          }
          return 1;
        }
      }
    }

    /**
     * Performs tryLock for write, enabling barging in both modes.
     * This is identical in effect to tryAcquire except for lack
     * of calls to writerShouldBlock.
     */
    final boolean tryWriteLock() {
      Thread current = Thread.currentThread();
      int c = getState();
      if (c != 0) {
        int w = exclusiveCount(c);
        if (w == 0 || current != getExclusiveOwnerThread()) {
          return false;
        }
        if (w == MAX_COUNT) {
          throw new Error("Maximum lock count exceeded");
        }
      }
      if (!compareAndSetState(c, c + 1)) {
        return false;
      }
      setExclusiveOwnerThread(current);
      return true;
    }

    /**
     * Performs tryLock for read, enabling barging in both modes.
     * This is identical in effect to tryAcquireShared except for
     * lack of calls to readerShouldBlock.
     */
    final boolean tryReadLock() {
      Thread current = Thread.currentThread();
      for (; ; ) {
        int c = getState();
        if (exclusiveCount(c) != 0 &&
            getExclusiveOwnerThread() != current) {
          return false;
        }
        int r = sharedCount(c);
        if (r == MAX_COUNT) {
          throw new Error("Maximum lock count exceeded");
        }
        if (compareAndSetState(c, c + SHARED_UNIT)) {
          if (r == 0) {
            firstReader = current;
            firstReaderHoldCount = 1;
          } else if (firstReader == current) {
            firstReaderHoldCount++;
          } else {
            HoldCounter rh = cachedHoldCounter;
            if (rh == null || rh.tid != getThreadId(current)) {
              cachedHoldCounter = rh = readHolds.get();
            } else if (rh.count == 0) {
              readHolds.set(rh);
            }
            rh.count++;
          }
          return true;
        }
      }
    }

    protected final boolean isHeldExclusively() {
      // While we must in general read state before owner,
      // we don't need to do so to check if current thread is owner
      return getExclusiveOwnerThread() == Thread.currentThread();
    }

    // Methods relayed to outer class

    final ConditionObject newCondition() {
      return new ConditionObject();
    }

    final Thread getOwner() {
      // Must read state before owner to ensure memory consistency
      return ((exclusiveCount(getState()) == 0) ?
          null :
          getExclusiveOwnerThread());
    }

    final int getReadLockCount() {
      return sharedCount(getState());
    }

    final boolean isWriteLocked() {
      return exclusiveCount(getState()) != 0;
    }

    final int getWriteHoldCount() {
      return isHeldExclusively() ? exclusiveCount(getState()) : 0;
    }

    final int getReadHoldCount() {
      if (getReadLockCount() == 0) {
        return 0;
      }

      Thread current = Thread.currentThread();
      if (firstReader == current) {
        return firstReaderHoldCount;
      }

      HoldCounter rh = cachedHoldCounter;
      if (rh != null && rh.tid == getThreadId(current)) {
        return rh.count;
      }

      int count = readHolds.get().count;
      if (count == 0) {
        readHolds.remove();
      }
      return count;
    }

    /**
     * Reconstitutes the instance from a stream (that is, deserializes it).
     */
    private void readObject(java.io.ObjectInputStream s)
        throws java.io.IOException, ClassNotFoundException {
      s.defaultReadObject();
      readHolds = new ThreadLocalHoldCounter();
      setState(0); // reset to unlocked state
    }

    final int getCount() {
      return getState();
    }
  }

  /**
   * Nonfair version of Sync
   */
  static final class NonfairSync extends Sync {

    private static final long serialVersionUID = -8159625535654395037L;

    final boolean writerShouldBlock() {
      return false; // writers can always barge
    }

    final boolean readerShouldBlock() {
            /* As a heuristic to avoid indefinite writer starvation,
             * block if the thread that momentarily appears to be head
             * of queue, if one exists, is a waiting writer.  This is
             * only a probabilistic effect since a new reader will not
             * block if there is a waiting writer behind other enabled
             * readers that have not yet drained from the queue.
             */
      return apparentlyFirstQueuedIsExclusive();
    }
  }

  /**
   * Fair version of Sync
   */
  static final class FairSync extends Sync {

    private static final long serialVersionUID = -2274990926593161451L;

    final boolean writerShouldBlock() {
      return hasQueuedPredecessors();
    }

    final boolean readerShouldBlock() {
      return hasQueuedPredecessors();
    }
  }

  /**
   * The lock returned by method {@link ReentrantReadWriteLock#readLock}.
   */
  public static class ReadLock implements Lock, java.io.Serializable {

    private static final long serialVersionUID = -5992448646407690164L;
    private final Sync sync;

    /**
     * Constructor for use by subclasses
     *
     * @param lock the outer lock object
     * @throws NullPointerException if the lock is null
     */
    protected ReadLock(ReentrantReadWriteLock lock) {
      sync = lock.sync;
    }

    /**
     * Acquires the read lock.
     *
     * <p>Acquires the read lock if the write lock is not held by
     * another thread and returns immediately.
     *
     * <p>If the write lock is held by another thread then
     * the current thread becomes disabled for thread scheduling
     * purposes and lies dormant until the read lock has been acquired.
     */
    public void lock() {
      sync.acquireShared(1);
    }

    /**
     * Acquires the read lock unless the current thread is
     * {@linkplain Thread#interrupt interrupted}.
     *
     * <p>Acquires the read lock if the write lock is not held
     * by another thread and returns immediately.
     *
     * <p>If the write lock is held by another thread then the
     * current thread becomes disabled for thread scheduling
     * purposes and lies dormant until one of two things happens:
     *
     * <ul>
     *
     * <li>The read lock is acquired by the current thread; or
     *
     * <li>Some other thread {@linkplain Thread#interrupt interrupts}
     * the current thread.
     *
     * </ul>
     *
     * <p>If the current thread:
     *
     * <ul>
     *
     * <li>has its interrupted status set on entry to this method; or
     *
     * <li>is {@linkplain Thread#interrupt interrupted} while
     * acquiring the read lock,
     *
     * </ul>
     *
     * then {@link InterruptedException} is thrown and the current
     * thread's interrupted status is cleared.
     *
     * <p>In this implementation, as this method is an explicit
     * interruption point, preference is given to responding to
     * the interrupt over normal or reentrant acquisition of the
     * lock.
     *
     * @throws InterruptedException if the current thread is interrupted
     */
    public void lockInterruptibly() throws InterruptedException {
      sync.acquireSharedInterruptibly(1);
    }

    /**
     * Acquires the read lock only if the write lock is not held by
     * another thread at the time of invocation.
     *
     * <p>Acquires the read lock if the write lock is not held by
     * another thread and returns immediately with the value
     * {@code true}. Even when this lock has been set to use a
     * fair ordering policy, a call to {@code tryLock()}
     * <em>will</em> immediately acquire the read lock if it is
     * available, whether or not other threads are currently
     * waiting for the read lock.  This &quot;barging&quot; behavior
     * can be useful in certain circumstances, even though it
     * breaks fairness. If you want to honor the fairness setting
     * for this lock, then use {@link #tryLock(long, TimeUnit)
     * tryLock(0, TimeUnit.SECONDS) } which is almost equivalent
     * (it also detects interruption).
     *
     * <p>If the write lock is held by another thread then
     * this method will return immediately with the value
     * {@code false}.
     *
     * @return {@code true} if the read lock was acquired
     */
    public boolean tryLock() {
      return sync.tryReadLock();
    }

    /**
     * Acquires the read lock if the write lock is not held by
     * another thread within the given waiting time and the
     * current thread has not been {@linkplain Thread#interrupt
     * interrupted}.
     *
     * <p>Acquires the read lock if the write lock is not held by
     * another thread and returns immediately with the value
     * {@code true}. If this lock has been set to use a fair
     * ordering policy then an available lock <em>will not</em> be
     * acquired if any other threads are waiting for the
     * lock. This is in contrast to the {@link #tryLock()}
     * method. If you want a timed {@code tryLock} that does
     * permit barging on a fair lock then combine the timed and
     * un-timed forms together:
     *
     * <pre> {@code
     * if (lock.tryLock() ||
     *     lock.tryLock(timeout, unit)) {
     *   ...
     * }}</pre>
     *
     * <p>If the write lock is held by another thread then the
     * current thread becomes disabled for thread scheduling
     * purposes and lies dormant until one of three things happens:
     *
     * <ul>
     *
     * <li>The read lock is acquired by the current thread; or
     *
     * <li>Some other thread {@linkplain Thread#interrupt interrupts}
     * the current thread; or
     *
     * <li>The specified waiting time elapses.
     *
     * </ul>
     *
     * <p>If the read lock is acquired then the value {@code true} is
     * returned.
     *
     * <p>If the current thread:
     *
     * <ul>
     *
     * <li>has its interrupted status set on entry to this method; or
     *
     * <li>is {@linkplain Thread#interrupt interrupted} while
     * acquiring the read lock,
     *
     * </ul> then {@link InterruptedException} is thrown and the
     * current thread's interrupted status is cleared.
     *
     * <p>If the specified waiting time elapses then the value
     * {@code false} is returned.  If the time is less than or
     * equal to zero, the method will not wait at all.
     *
     * <p>In this implementation, as this method is an explicit
     * interruption point, preference is given to responding to
     * the interrupt over normal or reentrant acquisition of the
     * lock, and over reporting the elapse of the waiting time.
     *
     * @param timeout the time to wait for the read lock
     * @param unit the time unit of the timeout argument
     * @return {@code true} if the read lock was acquired
     * @throws InterruptedException if the current thread is interrupted
     * @throws NullPointerException if the time unit is null
     */
    public boolean tryLock(long timeout, TimeUnit unit)
        throws InterruptedException {
      return sync.tryAcquireSharedNanos(1, unit.toNanos(timeout));
    }

    /**
     * Attempts to release this lock.
     *
     * <p>If the number of readers is now zero then the lock
     * is made available for write lock attempts.
     */
    public void unlock() {
      sync.releaseShared(1);
    }

    /**
     * Throws {@code UnsupportedOperationException} because
     * {@code ReadLocks} do not support conditions.
     *
     * @throws UnsupportedOperationException always
     */
    public Condition newCondition() {
      throw new UnsupportedOperationException();
    }

    /**
     * Returns a string identifying this lock, as well as its lock state.
     * The state, in brackets, includes the String {@code "Read locks ="}
     * followed by the number of held read locks.
     *
     * @return a string identifying this lock, as well as its lock state
     */
    public String toString() {
      int r = sync.getReadLockCount();
      return super.toString() +
          "[Read locks = " + r + "]";
    }
  }

  /**
   * The lock returned by method {@link ReentrantReadWriteLock#writeLock}.
   */
  public static class WriteLock implements Lock, java.io.Serializable {

    private static final long serialVersionUID = -4992448646407690164L;
    private final Sync sync;

    /**
     * Constructor for use by subclasses
     *
     * @param lock the outer lock object
     * @throws NullPointerException if the lock is null
     */
    protected WriteLock(ReentrantReadWriteLock lock) {
      sync = lock.sync;
    }

    /**
     * Acquires the write lock.
     *
     * <p>Acquires the write lock if neither the read nor write lock
     * are held by another thread
     * and returns immediately, setting the write lock hold count to
     * one.
     *
     * <p>If the current thread already holds the write lock then the
     * hold count is incremented by one and the method returns
     * immediately.
     *
     * <p>If the lock is held by another thread then the current
     * thread becomes disabled for thread scheduling purposes and
     * lies dormant until the write lock has been acquired, at which
     * time the write lock hold count is set to one.
     */
    public void lock() {
      sync.acquire(1);
    }

    /**
     * Acquires the write lock unless the current thread is
     * {@linkplain Thread#interrupt interrupted}.
     *
     * <p>Acquires the write lock if neither the read nor write lock
     * are held by another thread
     * and returns immediately, setting the write lock hold count to
     * one.
     *
     * <p>If the current thread already holds this lock then the
     * hold count is incremented by one and the method returns
     * immediately.
     *
     * <p>If the lock is held by another thread then the current
     * thread becomes disabled for thread scheduling purposes and
     * lies dormant until one of two things happens:
     *
     * <ul>
     *
     * <li>The write lock is acquired by the current thread; or
     *
     * <li>Some other thread {@linkplain Thread#interrupt interrupts}
     * the current thread.
     *
     * </ul>
     *
     * <p>If the write lock is acquired by the current thread then the
     * lock hold count is set to one.
     *
     * <p>If the current thread:
     *
     * <ul>
     *
     * <li>has its interrupted status set on entry to this method;
     * or
     *
     * <li>is {@linkplain Thread#interrupt interrupted} while
     * acquiring the write lock,
     *
     * </ul>
     *
     * then {@link InterruptedException} is thrown and the current
     * thread's interrupted status is cleared.
     *
     * <p>In this implementation, as this method is an explicit
     * interruption point, preference is given to responding to
     * the interrupt over normal or reentrant acquisition of the
     * lock.
     *
     * @throws InterruptedException if the current thread is interrupted
     */
    public void lockInterruptibly() throws InterruptedException {
      sync.acquireInterruptibly(1);
    }

    /**
     * Acquires the write lock only if it is not held by another thread
     * at the time of invocation.
     *
     * <p>Acquires the write lock if neither the read nor write lock
     * are held by another thread
     * and returns immediately with the value {@code true},
     * setting the write lock hold count to one. Even when this lock has
     * been set to use a fair ordering policy, a call to
     * {@code tryLock()} <em>will</em> immediately acquire the
     * lock if it is available, whether or not other threads are
     * currently waiting for the write lock.  This &quot;barging&quot;
     * behavior can be useful in certain circumstances, even
     * though it breaks fairness. If you want to honor the
     * fairness setting for this lock, then use {@link
     * #tryLock(long, TimeUnit) tryLock(0, TimeUnit.SECONDS) }
     * which is almost equivalent (it also detects interruption).
     *
     * <p>If the current thread already holds this lock then the
     * hold count is incremented by one and the method returns
     * {@code true}.
     *
     * <p>If the lock is held by another thread then this method
     * will return immediately with the value {@code false}.
     *
     * @return {@code true} if the lock was free and was acquired by the current thread, or the
     * write lock was already held by the current thread; and {@code false} otherwise.
     */
    public boolean tryLock() {
      return sync.tryWriteLock();
    }

    /**
     * Acquires the write lock if it is not held by another thread
     * within the given waiting time and the current thread has
     * not been {@linkplain Thread#interrupt interrupted}.
     *
     * <p>Acquires the write lock if neither the read nor write lock
     * are held by another thread
     * and returns immediately with the value {@code true},
     * setting the write lock hold count to one. If this lock has been
     * set to use a fair ordering policy then an available lock
     * <em>will not</em> be acquired if any other threads are
     * waiting for the write lock. This is in contrast to the {@link
     * #tryLock()} method. If you want a timed {@code tryLock}
     * that does permit barging on a fair lock then combine the
     * timed and un-timed forms together:
     *
     * <pre> {@code
     * if (lock.tryLock() ||
     *     lock.tryLock(timeout, unit)) {
     *   ...
     * }}</pre>
     *
     * <p>If the current thread already holds this lock then the
     * hold count is incremented by one and the method returns
     * {@code true}.
     *
     * <p>If the lock is held by another thread then the current
     * thread becomes disabled for thread scheduling purposes and
     * lies dormant until one of three things happens:
     *
     * <ul>
     *
     * <li>The write lock is acquired by the current thread; or
     *
     * <li>Some other thread {@linkplain Thread#interrupt interrupts}
     * the current thread; or
     *
     * <li>The specified waiting time elapses
     *
     * </ul>
     *
     * <p>If the write lock is acquired then the value {@code true} is
     * returned and the write lock hold count is set to one.
     *
     * <p>If the current thread:
     *
     * <ul>
     *
     * <li>has its interrupted status set on entry to this method;
     * or
     *
     * <li>is {@linkplain Thread#interrupt interrupted} while
     * acquiring the write lock,
     *
     * </ul>
     *
     * then {@link InterruptedException} is thrown and the current
     * thread's interrupted status is cleared.
     *
     * <p>If the specified waiting time elapses then the value
     * {@code false} is returned.  If the time is less than or
     * equal to zero, the method will not wait at all.
     *
     * <p>In this implementation, as this method is an explicit
     * interruption point, preference is given to responding to
     * the interrupt over normal or reentrant acquisition of the
     * lock, and over reporting the elapse of the waiting time.
     *
     * @param timeout the time to wait for the write lock
     * @param unit the time unit of the timeout argument
     * @return {@code true} if the lock was free and was acquired by the current thread, or the
     * write lock was already held by the current thread; and {@code false} if the waiting time
     * elapsed before the lock could be acquired.
     * @throws InterruptedException if the current thread is interrupted
     * @throws NullPointerException if the time unit is null
     */
    public boolean tryLock(long timeout, TimeUnit unit)
        throws InterruptedException {
      return sync.tryAcquireNanos(1, unit.toNanos(timeout));
    }

    /**
     * Attempts to release this lock.
     *
     * <p>If the current thread is the holder of this lock then
     * the hold count is decremented. If the hold count is now
     * zero then the lock is released.  If the current thread is
     * not the holder of this lock then {@link
     * IllegalMonitorStateException} is thrown.
     *
     * @throws IllegalMonitorStateException if the current thread does not hold this lock
     */
    public void unlock() {
      sync.release(1);
    }

    /**
     * Returns a {@link Condition} instance for use with this
     * {@link Lock} instance.
     * <p>The returned {@link Condition} instance supports the same
     * usages as do the {@link Object} monitor methods ({@link
     * Object#wait() wait}, {@link Object#notify notify}, and {@link
     * Object#notifyAll notifyAll}) when used with the built-in
     * monitor lock.
     *
     * <ul>
     *
     * <li>If this write lock is not held when any {@link
     * Condition} method is called then an {@link
     * IllegalMonitorStateException} is thrown.  (Read locks are
     * held independently of write locks, so are not checked or
     * affected. However it is essentially always an error to
     * invoke a condition waiting method when the current thread
     * has also acquired read locks, since other threads that
     * could unblock it will not be able to acquire the write
     * lock.)
     *
     * <li>When the condition {@linkplain Condition#await() waiting}
     * methods are called the write lock is released and, before
     * they return, the write lock is reacquired and the lock hold
     * count restored to what it was when the method was called.
     *
     * <li>If a thread is {@linkplain Thread#interrupt interrupted} while
     * waiting then the wait will terminate, an {@link
     * InterruptedException} will be thrown, and the thread's
     * interrupted status will be cleared.
     *
     * <li> Waiting threads are signalled in FIFO order.
     *
     * <li>The ordering of lock reacquisition for threads returning
     * from waiting methods is the same as for threads initially
     * acquiring the lock, which is in the default case not specified,
     * but for <em>fair</em> locks favors those threads that have been
     * waiting the longest.
     *
     * </ul>
     *
     * @return the Condition object
     */
    public Condition newCondition() {
      return sync.newCondition();
    }

    /**
     * Returns a string identifying this lock, as well as its lock
     * state.  The state, in brackets includes either the String
     * {@code "Unlocked"} or the String {@code "Locked by"}
     * followed by the {@linkplain Thread#getName name} of the owning thread.
     *
     * @return a string identifying this lock, as well as its lock state
     */
    public String toString() {
      Thread o = sync.getOwner();
      return super.toString() + ((o == null) ?
          "[Unlocked]" :
          "[Locked by thread " + o.getName() + "]");
    }

    /**
     * Queries if this write lock is held by the current thread.
     * Identical in effect to {@link
     * ReentrantReadWriteLock#isWriteLockedByCurrentThread}.
     *
     * @return {@code true} if the current thread holds this lock and {@code false} otherwise
     * @since 1.6
     */
    public boolean isHeldByCurrentThread() {
      return sync.isHeldExclusively();
    }

    /**
     * Queries the number of holds on this write lock by the current
     * thread.  A thread has a hold on a lock for each lock action
     * that is not matched by an unlock action.  Identical in effect
     * to {@link ReentrantReadWriteLock#getWriteHoldCount}.
     *
     * @return the number of holds on this lock by the current thread, or zero if this lock is not
     * held by the current thread
     * @since 1.6
     */
    public int getHoldCount() {
      return sync.getWriteHoldCount();
    }
  }

  // Instrumentation and status

  /**
   * Returns {@code true} if this lock has fairness set true.
   *
   * @return {@code true} if this lock has fairness set true
   */
  public final boolean isFair() {
    return sync instanceof FairSync;
  }

  /**
   * Returns the thread that currently owns the write lock, or
   * {@code null} if not owned. When this method is called by a
   * thread that is not the owner, the return value reflects a
   * best-effort approximation of current lock status. For example,
   * the owner may be momentarily {@code null} even if there are
   * threads trying to acquire the lock but have not yet done so.
   * This method is designed to facilitate construction of
   * subclasses that provide more extensive lock monitoring
   * facilities.
   *
   * @return the owner, or {@code null} if not owned
   */
  protected Thread getOwner() {
    return sync.getOwner();
  }

  /**
   * Queries the number of read locks held for this lock. This
   * method is designed for use in monitoring system state, not for
   * synchronization control.
   *
   * @return the number of read locks held
   */
  public int getReadLockCount() {
    return sync.getReadLockCount();
  }

  /**
   * Queries if the write lock is held by any thread. This method is
   * designed for use in monitoring system state, not for
   * synchronization control.
   *
   * @return {@code true} if any thread holds the write lock and {@code false} otherwise
   */
  public boolean isWriteLocked() {
    return sync.isWriteLocked();
  }

  /**
   * Queries if the write lock is held by the current thread.
   *
   * @return {@code true} if the current thread holds the write lock and {@code false} otherwise
   */
  public boolean isWriteLockedByCurrentThread() {
    return sync.isHeldExclusively();
  }

  /**
   * Queries the number of reentrant write holds on this lock by the
   * current thread.  A writer thread has a hold on a lock for
   * each lock action that is not matched by an unlock action.
   *
   * @return the number of holds on the write lock by the current thread, or zero if the write lock
   * is not held by the current thread
   */
  public int getWriteHoldCount() {
    return sync.getWriteHoldCount();
  }

  /**
   * Queries the number of reentrant read holds on this lock by the
   * current thread.  A reader thread has a hold on a lock for
   * each lock action that is not matched by an unlock action.
   *
   * @return the number of holds on the read lock by the current thread, or zero if the read lock is
   * not held by the current thread
   * @since 1.6
   */
  public int getReadHoldCount() {
    return sync.getReadHoldCount();
  }

  /**
   * Returns a collection containing threads that may be waiting to
   * acquire the write lock.  Because the actual set of threads may
   * change dynamically while constructing this result, the returned
   * collection is only a best-effort estimate.  The elements of the
   * returned collection are in no particular order.  This method is
   * designed to facilitate construction of subclasses that provide
   * more extensive lock monitoring facilities.
   *
   * @return the collection of threads
   */
  protected Collection<Thread> getQueuedWriterThreads() {
    return sync.getExclusiveQueuedThreads();
  }

  /**
   * Returns a collection containing threads that may be waiting to
   * acquire the read lock.  Because the actual set of threads may
   * change dynamically while constructing this result, the returned
   * collection is only a best-effort estimate.  The elements of the
   * returned collection are in no particular order.  This method is
   * designed to facilitate construction of subclasses that provide
   * more extensive lock monitoring facilities.
   *
   * @return the collection of threads
   */
  protected Collection<Thread> getQueuedReaderThreads() {
    return sync.getSharedQueuedThreads();
  }

  /**
   * Queries whether any threads are waiting to acquire the read or
   * write lock. Note that because cancellations may occur at any
   * time, a {@code true} return does not guarantee that any other
   * thread will ever acquire a lock.  This method is designed
   * primarily for use in monitoring of the system state.
   *
   * @return {@code true} if there may be other threads waiting to acquire the lock
   */
  public final boolean hasQueuedThreads() {
    return sync.hasQueuedThreads();
  }

  /**
   * Queries whether the given thread is waiting to acquire either
   * the read or write lock. Note that because cancellations may
   * occur at any time, a {@code true} return does not guarantee
   * that this thread will ever acquire a lock.  This method is
   * designed primarily for use in monitoring of the system state.
   *
   * @param thread the thread
   * @return {@code true} if the given thread is queued waiting for this lock
   * @throws NullPointerException if the thread is null
   */
  public final boolean hasQueuedThread(Thread thread) {
    return sync.isQueued(thread);
  }

  /**
   * Returns an estimate of the number of threads waiting to acquire
   * either the read or write lock.  The value is only an estimate
   * because the number of threads may change dynamically while this
   * method traverses internal data structures.  This method is
   * designed for use in monitoring of the system state, not for
   * synchronization control.
   *
   * @return the estimated number of threads waiting for this lock
   */
  public final int getQueueLength() {
    return sync.getQueueLength();
  }

  /**
   * Returns a collection containing threads that may be waiting to
   * acquire either the read or write lock.  Because the actual set
   * of threads may change dynamically while constructing this
   * result, the returned collection is only a best-effort estimate.
   * The elements of the returned collection are in no particular
   * order.  This method is designed to facilitate construction of
   * subclasses that provide more extensive monitoring facilities.
   *
   * @return the collection of threads
   */
  protected Collection<Thread> getQueuedThreads() {
    return sync.getQueuedThreads();
  }

  /**
   * Queries whether any threads are waiting on the given condition
   * associated with the write lock. Note that because timeouts and
   * interrupts may occur at any time, a {@code true} return does
   * not guarantee that a future {@code signal} will awaken any
   * threads.  This method is designed primarily for use in
   * monitoring of the system state.
   *
   * @param condition the condition
   * @return {@code true} if there are any waiting threads
   * @throws IllegalMonitorStateException if this lock is not held
   * @throws IllegalArgumentException if the given condition is not associated with this lock
   * @throws NullPointerException if the condition is null
   */
  public boolean hasWaiters(Condition condition) {
    if (condition == null) {
      throw new NullPointerException();
    }
    if (!(condition instanceof AbstractQueuedSynchronizer.ConditionObject)) {
      throw new IllegalArgumentException("not owner");
    }
    return sync.hasWaiters((AbstractQueuedSynchronizer.ConditionObject) condition);
  }

  /**
   * Returns an estimate of the number of threads waiting on the
   * given condition associated with the write lock. Note that because
   * timeouts and interrupts may occur at any time, the estimate
   * serves only as an upper bound on the actual number of waiters.
   * This method is designed for use in monitoring of the system
   * state, not for synchronization control.
   *
   * @param condition the condition
   * @return the estimated number of waiting threads
   * @throws IllegalMonitorStateException if this lock is not held
   * @throws IllegalArgumentException if the given condition is not associated with this lock
   * @throws NullPointerException if the condition is null
   */
  public int getWaitQueueLength(Condition condition) {
    if (condition == null) {
      throw new NullPointerException();
    }
    if (!(condition instanceof AbstractQueuedSynchronizer.ConditionObject)) {
      throw new IllegalArgumentException("not owner");
    }
    return sync.getWaitQueueLength((AbstractQueuedSynchronizer.ConditionObject) condition);
  }

  /**
   * Returns a collection containing those threads that may be
   * waiting on the given condition associated with the write lock.
   * Because the actual set of threads may change dynamically while
   * constructing this result, the returned collection is only a
   * best-effort estimate. The elements of the returned collection
   * are in no particular order.  This method is designed to
   * facilitate construction of subclasses that provide more
   * extensive condition monitoring facilities.
   *
   * @param condition the condition
   * @return the collection of threads
   * @throws IllegalMonitorStateException if this lock is not held
   * @throws IllegalArgumentException if the given condition is not associated with this lock
   * @throws NullPointerException if the condition is null
   */
  protected Collection<Thread> getWaitingThreads(Condition condition) {
    if (condition == null) {
      throw new NullPointerException();
    }
    if (!(condition instanceof AbstractQueuedSynchronizer.ConditionObject)) {
      throw new IllegalArgumentException("not owner");
    }
    return sync.getWaitingThreads((AbstractQueuedSynchronizer.ConditionObject) condition);
  }

  /**
   * Returns a string identifying this lock, as well as its lock state.
   * The state, in brackets, includes the String {@code "Write locks ="}
   * followed by the number of reentrantly held write locks, and the
   * String {@code "Read locks ="} followed by the number of held
   * read locks.
   *
   * @return a string identifying this lock, as well as its lock state
   */
  public String toString() {
    int c = sync.getCount();
    int w = Sync.exclusiveCount(c);
    int r = Sync.sharedCount(c);

    return super.toString() +
        "[Write locks = " + w + ", Read locks = " + r + "]";
  }

  /**
   * Returns the thread id for the given thread.  We must access
   * this directly rather than via method Thread.getId() because
   * getId() is not final, and has been known to be overridden in
   * ways that do not preserve unique mappings.
   */
  static final long getThreadId(Thread thread) {
    return UNSAFE.getLongVolatile(thread, TID_OFFSET);
  }

  // Unsafe mechanics
  private static final sun.misc.Unsafe UNSAFE;
  private static final long TID_OFFSET;

  static {
    try {
      UNSAFE = sun.misc.Unsafe.getUnsafe();
      Class<?> tk = Thread.class;
      TID_OFFSET = UNSAFE.objectFieldOffset
          (tk.getDeclaredField("tid"));
    } catch (Exception e) {
      throw new Error(e);
    }
  }

}
